class Solution
{
public:
    int minCapability(vector<int> &nums, int k)
    {
        int n = nums.size();
        vector<int> id(n);
        iota(id.begin(), id.end(), 0);
        sort(id.begin(), id.end(), [&](int i, int j)
             { return nums[i] < nums[j]; });
        int canTakeCount = (n + 1) / 2;
        set<int> noTake{-1, n};
        for (int i = n - 1; i >= 0; --i)
        {
            int maxId = id[i];
            auto it = noTake.lower_bound(maxId);
            int r = *it;
            int l = *(--it);
            canTakeCount -= (r - l) / 2;
            canTakeCount += (r - maxId) / 2;
            canTakeCount += (maxId - l) / 2;
            if (canTakeCount < k)
            {
                return nums[maxId];
            }
            noTake.insert(maxId);
        }
        return 0;
    }
};